The present invention relates, in general, to information processing system organization and, in particular, to flow controlling.
Any network of items may be represented as a graph using nodes and links, where each node represents an item in the network, and where each link represents a connection from one node to another. Examples of such networks include telephone networks, integrated circuits, computer networks, infrastructure networks (e.g., roads, trains, etc.), and so on.
The ability to analyze the links and nodes in a graph according to certain criteria is useful for many different purposes. For example, a electric company may wish to isolate, or remove, a substation from its power grid due to a malfunction at that substation. A designer may wish to determine the optimum placement of circuit components on an integrated circuit to optimize circuit performance. Operators of a computer network (e.g., the INTERNET) may wish to isolate a computer from the network if the computer become infected with a virus and thus prevent other computers in the network from becoming infected with the virus. A set of links or nodes to be removed from a graph to isolate one node from another node is often referred to as a cutset.
In an article entitled xe2x80x9cVertex Cutsets of Undirected Graphs,xe2x80x9d published June 1995, in IEEE Transactions on Reliability, Vol. 44, No. 2, C. Patvardhan et al. disclosed a method of identifying every possible cutset for isolating two nodes from one another, regardless of the cost associated with cutting a node or link. Since the number of possible cutsets for isolating two nodes from one another grows exponentially as the number of nodes and/or links increases, the method disclosed by Patvardhan et al. becomes computationally prohibitive when dealing with a large network. The present invention discloses a computationally efficient method of finding links and, possibly, nodes, that cost the least to cut, or eliminate, to isolate two user-selected nodes from each other.
In an article entitled xe2x80x9cExperimental Study of Minimum Cut Algorithms,xe2x80x9d published 1997, in Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, Chandra S. Chekuri et al. disclosed a survey of the most efficient cutset algorithms available in 1997. The algorithms disclosed therein find one cutset that minimizes the cost associated with cutting the links, but do not find all of the possible cutsets that minimize the cost associated with cutting the links as does the present invention.
U.S. Pat. No. 5,666,290, entitled xe2x80x9cINTERACTIVE TIME-DRIVEN METHOD OF COMPONENT PLACEMENT THAT MORE DIRECTLY CONSTRAINS CRITICAL PATHS USING NET-BASED CONSTRAINTS,xe2x80x9d discloses a method of placing circuit components on an integrated circuit to optimize circuit performance by finding one cutset that minimizes cost. U.S. Pat. No. 5,666,290 does not disclose a method of finding all cutsets that minimize cost as does the present invention. U.S. Pat. No.5,666,290 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,748,844, entitled xe2x80x9cGRAPH PARTITIONING SYSTEM,xe2x80x9d discloses a device for partitioning a graph by starting with 100 cutsets, reducing the 100 to the best 20 and picking the best cutset therefrom. U.S. Pat. No. 5,748,844 does not disclose a method of finding all minimum cost cutsets as does the present invention. U.S. Pat. No. 5,748,844 is hereby incorporated by reference into the specification of the present invention.
It is an object of the present invention to identify, in a computationally-efficient manner, all minimum-cost cutsets in a network to isolate one node in the network from another node.
It is an object of the present invention to identify, in a computationally-efficient manner, all minimum-cost cutsets in a network to isolate one node in the network from another node, where the network is any suitable network such as a computer network, a telephone network, an infrastructure network, an integrated-circuit interconnection network, and so on.
The present invention is the first method of identifying, in a computationally-efficient manner, all minimum-cost cutsets in a network to isolate one node in the network from another node. The present invention is applicable to any suitable network such as a computer network, a telephone network, an infrastructure network, an integrated circuit interconnection network, and so on.
The first step of the present invention is receiving a suitable network, where the network includes nodes and links between the nodes. The links may be unidirectional or bidirectional.
The second step is replacing each bidirectional link with two unidirectional links, where the two unidirectional links are parallel to each other and directed in opposite directions from each other.
The third step is assigning a non-negative value, or cost, to each node and link in the network. The cost assigned to each node or link is the cost of eliminating, or cutting, that node or link from the network.
The fourth step is choosing two nodes in the network, a source node S and a termination node T, between which it is desired to find all minimum-cost cutsets.
The fifth step is removing any extraneous nodes and links that are not along a path from node S to node T.
The sixth step is adding a node next to each node that is original to the network.
The seventh step is moving, for each node that is original to the network, the links directed away from the node to its added node so that such links are directed away from the added node.
The eighth step is adding, to each node that is original to the network, a link directed out of the node and directed into its added node.
The ninth step is assigning a non-negative value, or cost, to each link added in the last step that is equal to the non-negative value, or cost, of the corresponding node that is original to the network.
The tenth step is finding the paths from node S to node T in the network as modified by steps two through nine that maximize flow from node S to node T. The flow capacity of a node, or link, is equal to the cost assigned to that node, or link.
The eleventh step is creating a residual graph of the network as modified by steps two through nine by including all original nodes of the network; including all nodes added to the network; including all links, with direction maintained, from the network that were not identified in the previous step as being a part of a maximum-flow path; including all links, with directions reversed, from the network that were identified as being a part of a maximum-flow path and carried flow at capacity; including all links, with direction maintained, from the network that were identified as being a part of a maximum-flow path and carried flow at less than capacity; and adding a link, in the opposite direction, for each link from the network that was identified as being a part of a maximum-flow path and carried flow at less than capacity. The residual graph contains non-maximum-cost paths from node S to node T from which will be found all minimum-cost cutsets for the network.
The twelfth step is finding each set of nodes in the residual graph that includes node S, does not include node T, and does not include a link directed from a node within the set to a node outside of the set. A set of nodes that meets the three criteria listed above is commonly referred to as a closure. All minimum-cost cutsets of the network are found using the closures of the residual graph. The number of minimum-cost cutsets of the network is less than or equal to the number of closures of the residual graph.
The thirteenth step is finding in the network as modified by steps two through nine, for each closure, any link directed from a node within the closure to a node outside of the closure. Such a set of links found for one particular closure constitutes one possible minimum-cost cutset for the network. The sets of links found for all of the closures constitute all of the possible minimum-cost cutsets for the network. If a minimum-cost cutset includes a link between a node that is original to the network and its added node then the node that is original to the network must be eliminated because such a link is a theoretical construct used to find all of the minimum-cost cutsets and does not physically exist in the actual network.
The fourteenth step is selecting a minimum-cost cutset that is the most convenient cutset to act on from all of the minimum-cost cutsets found in the last step.
The fifteenth, and last, step is eliminating the links and nodes, as required by the minimum-cost cutset chosen in the last step, to isolate node S from node T.